In some computer systems, the size of a program to be executed may be subject to constraints. For example, the computer system may have a limited amount of memory in which to store the program. Techniques have been developed to compress the size of a program.
For example, one technique, often referred to as “Echo Technology,” replaces a set of instructions in a program with a single “Echo Instruction” which typically have the format “Echo (offset, length)”. The “offset” parameter may specify an offset between a location of a replaceable set of instructions (to be replaced by the single Echo Instruction) and a location of a target set of instructions that match the instructions in the replaceable set. The “length” parameter may specify a number of instructions in the replaceable set of instructions. When the Echo Instruction is executed, the “offset” parameter is used to cause control to branch to the location of the target set of instructions. Then, the processor begins to execute the instructions in the target set. The “length” parameter is used to determine when control should branch back to the instruction immediately following the Echo Instruction. Because many instructions can be replaced by a smaller number of Echo Instructions, this technique may help to reduce the size of a program.
An illustrative example will be described with reference to Tables 1 and 2. Table 1 lists instructions and their locations in an example set of program code. The set of instructions at locations 340 to 356 matches the set of instructions at locations 100 to 116. Thus, the instructions at locations 340 to 356 can be replaced by an Echo Instruction which indicates an offset of 240 (340 minus 100) and a length of 5. The instructions at locations 340 to 356 can be referred to as a replaceable set of instructions. Table 2 shows a list of instructions in which the instructions at locations 340 to 356 have been replaced by an Echo Instruction that indicates an offset of 240 and a length of 5. Thus, the Echo Instruction at location 340 points to the five instructions starting at the location 100, which may be referred to as a target set of instructions.
TABLE 1LocationInstruction100mov104shl108xor112add116movsx. . .. . .340mov344shl348xor352add356movsx. . .. . .404mov408shl412xor416add420movsx. . .. . .
TABLE 2LocationInstruction100mov104shl108xor112add116movsx. . .. . .340Echo(240, 5). . .. . .388mov392shl396xor400add404movsx. . .. . .
Because the five instructions at locations 340 to 356 have been replaced by a single Echo Instruction, the instructions that were at locations 404 to 420 (in Table 1) will now be at the locations 388 to 404 (Table 2). These instructions also match the set of instructions at locations 100 to 116. Thus, the instructions at locations 388 to 404 can be replaced by an Echo Instruction which indicates an offset of 288 (388 minus 100) and a length of 5. Table 3 shows a list of instructions in which the instructions at locations 388 to 404 have been replaced by an Echo Instruction that indicates an offset of 288 and a length of 5. Thus, the Echo Instruction at location 388 points to the five instructions starting at the location 100.
TABLE 3LocationInstruction100mov104shl108xor112add116movsx. . .. . .340Echo(240, 5). . .. . .388Echo(288, 5). . .. . .